﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RecommenderAlgorithmLibrary
{
    /// <summary>
    /// This algorithm follows the paper "A Personalized Recommender Integrating Item-based and User-based Collaborative Filtering"
    /// published on 2008 International Seminar on Business and Information Management by XiaoYan Shi,  HongWu Ye and SongJie Gong.
    /// This paper proposes a CF algorithm integrating the UBCF and IBCF, which takes both vertical and horizontal information in the
    /// user-item matrix. It produces perdition using IBCF to form a dense user-item matrix and then recommends items to a specific user using UBCF
    /// based on the dense matrix.
    /// </summary>
    public class IBCFandUBCFHybridAlgorithm
    {
        #region Main method

        /// <summary>
        /// This main method of this recommender algorithm. 
        /// </summary>
        /// <param name="originalRatings">The exsiting real user- item rating matrix</param>
        /// <param name="targetUserIndex">The index of target user in the rating matrix</param>
        /// <param name="recommendNumber">The number of items to recommend</param>
        /// <param name="TopN">The number of most similar neighbors.</param>
        /// <returns>The indexes of recommended items in the rating matrix</returns>
        public List<int> RecommendItems(int?[][] originalRatings, int targetUserIndex, int recommendNumber, int TOPN)
        {
            List<int> recommendedItemsIndexes = new List<int>();

            float?[][] itemSimilarities;
            float?[][] predictedRatings;
            float?[][] userSimilarities;
            float?[] targetUserFinalRatings;

            itemSimilarities = CalculateItemSimilarityUsingPearsonCorrelation(originalRatings);
            predictedRatings = PredictRatings(originalRatings, itemSimilarities, TOPN);
            userSimilarities = CalculateUserSimilarities(predictedRatings);
            targetUserFinalRatings = CalculateFinalUserRatings(targetUserIndex, originalRatings, userSimilarities[targetUserIndex], predictedRatings, TOPN);

            Dictionary<int, float?> indexAndRatings = new Dictionary<int, float?>();
            for (int i = 0; i < targetUserFinalRatings.Length; i++)
            {
                indexAndRatings.Add(i, targetUserFinalRatings[i]);
            }

            var sortedDictionary = indexAndRatings.OrderByDescending(i => i.Value);

            foreach (KeyValuePair<int, float?> keypair in sortedDictionary)
            {
                if(keypair.Value!=null)
                {
                    recommendedItemsIndexes.Add(keypair.Key);
                }
                if (recommendedItemsIndexes.Capacity >= recommendNumber)
                {
                    break;
                }
            }

            return recommendedItemsIndexes;
        }

        /// <summary>
        /// Predicts all unrated ratings in the original rating matrix. This method is used when for carrying on the experiment using dataset from movielens.
        /// </summary>
        /// <param name="originalRatings">The exsiting real user- item rating matrix</param>
        /// <param name="TOPN">The number of most similar neighbors.</param>
        /// <returns>The dense user item rating matrix contains all original ratings and predited ratings</returns>
        public float?[][] PredictAllRatings(int?[][] originalRatings, int TOPN)
        {
            float?[][] finalAllPredictedRatings;

            float?[][] itemSimilarities;
            float?[][] predictedRatings;
            float?[][] userSimilarities;

            itemSimilarities = CalculateItemSimilarityUsingPearsonCorrelation(originalRatings);
            predictedRatings = PredictRatings(originalRatings, itemSimilarities, TOPN);
            userSimilarities = CalculateUserSimilarities(predictedRatings);
            finalAllPredictedRatings = CalculateAllFinalRatings(originalRatings,userSimilarities, predictedRatings, TOPN);

            return finalAllPredictedRatings;
        }

        #endregion

        #region Public Methods

        /// <summary>
        /// Calculates the item similarities based on real user ratings using the cosine fomulation.
        /// </summary>
        /// <param name="ratings">The exsiting user- item rating matrix</param>
        /// <returns>A square matrix represents the item-item similarity</returns>
        public float?[][] CalculateItemSimilarityUsingCosine(int?[][] ratings)
        {
            int itemNumber = ratings[0].Length;
            float?[][] similarities = new float?[itemNumber][];

            for (int i = 0; i < itemNumber; i++)
            {
                float?[] sim = new float?[itemNumber];
                for (int j = 0; j < itemNumber; j++)
                {
                    if (i == j)
                    {
                        sim[j] = 1;
                    }
                    else
                    {
                        sim[j] = CosineItemSimilarity(i, j, ratings);
                    }
                }
                similarities[i] = sim;
            }

            return similarities;
        }

        /// <summary>
        /// Calculates the item similarities based on real user ratings using pearson correlation.
        /// </summary>
        /// <param name="ratings">The exsiting user- item rating matrix</param>
        /// <returns>A square matrix represents the item-item similarity</returns>
        public float?[][] CalculateItemSimilarityUsingPearsonCorrelation(int?[][] ratings)
        {
            int itemNumber = ratings[0].Length;
            float?[][] similarities = new float?[itemNumber][];

            float?[] averageRatings = CalculateItemAverageRatings(ratings);

            for (int i = 0; i < itemNumber; i++)
            {
                float?[] sim = new float?[itemNumber];
                for (int j = 0; j < itemNumber; j++)
                {
                    if (i == j)
                    {
                        sim[j] = 1;
                    }
                    else
                    {
                        sim[j] = PearsonCorrelationItemSimilarity(i, j, ratings, averageRatings);
                    }
                }
                similarities[i] = sim;
            }

            return similarities;
        }

        /// <summary>
        /// Predicts ratings to fill the user-item rating matrix using item based CF.
        /// </summary>
        /// <param name="originalRatings">The exsiting real user- item rating matrix</param>
        /// <param name="similarities">The items similarity square matrix.</param>
        /// <param name="TopN">The number of most similar neighbors.</param>
        /// <returns>The dense user-item ratings matrix contains both user rated ratings and predicted ratings.</returns>
        public float?[][] PredictRatings(int?[][] originalRatings, float?[][] similarities, int TopN)
        {
            int userNumber = originalRatings.Length;
            int itemNumber = originalRatings[0].Length;

            float?[][] predictedRatings = new float?[userNumber][];

            for (int i = 0; i < userNumber; i++)
            {
                float?[] ratings = new float?[itemNumber];
                for (int j = 0; j < itemNumber; j++)
                {
                    float rating;
                    if (originalRatings[i][j] == null)
                    {
                        rating = PredictRating(originalRatings[i], similarities[j], TopN);
                    }
                    else
                    {
                        rating = (float)originalRatings[i][j];
                    }
                    ratings[j] = rating;
                }
                predictedRatings[i] = ratings;
            }

            return predictedRatings;
        }

        /// <summary>
        /// Calculates user similarities based on the dense rating matrix.
        /// </summary>
        /// <param name="originalRatings">The exsiting real user- item rating matrix</param>
        /// <param name="predictedRatings">The dense user-item ratings matrix contains both user rated ratings and predicted ratings.</param>
        /// <returns>The user-user similarities square matrix.</returns>
        public float?[][] CalculateUserSimilarities(float?[][] predictedRatings)
        {
            int userNumber = predictedRatings.Length;

            float?[][] userSimilarities = new float?[userNumber][];

            float?[] userAverageRatings = CalculateUserAverageRatings(predictedRatings);

            for (int i = 0; i < userNumber; i++)
            {
                float?[] similarities = new float?[userNumber];
                for (int j = 0; j < userNumber; j++)
                {
                    float? similarity = null;
                    if (i == j)
                    {
                        similarity = 1;
                    }
                    else
                    {
                        if ((userAverageRatings[i] != null) && (userAverageRatings[j] != null))
                        {
                            similarity = CalculateTwoUserSimilarity(userAverageRatings[i], userAverageRatings[j], predictedRatings[i], predictedRatings[j]);
                        }
                    }
                    similarities[j] = similarity;
                }
                userSimilarities[i] = similarities;
            }

            return userSimilarities;

        }

        /// <summary>
        /// Calculates the final ratings of items to target user.
        /// </summary>
        /// <param name="userIndex">The index of target user in user-item rating matrix.</param>
        /// <param name="originalRatings">The exsiting real user- item rating matrix</param>
        /// <param name="targetUserSimilarities">The similarities of target user to other users.</param>
        /// <param name="predictedRatings">The dense user-item ratings matrix contains both user rated ratings and predicted ratings.</param>
        /// <param name="topN">The number of most similar neighbors.</param>
        /// <returns>The final ratings of target user to every items, contains both real ratings and predicted ratings.</returns>
        public float?[] CalculateFinalUserRatings(int userIndex, int?[][] originalRatings, float?[] targetUserSimilarities, float?[][] predictedRatings, int topN)
        {
            int userNumber = predictedRatings.Length;
            int itemNumber = predictedRatings[0].Length;

            float?[] finalRatings = new float?[itemNumber];
            float?[] userAverageRatings = CalculateUserAverageRatings(predictedRatings);
            float targetUserAverageRating = userAverageRatings[userIndex].Value;
            int?[] userOriginalRatings = originalRatings[userIndex];

            //Stores the indexes of selected users and their similarities to target user.
            Dictionary<int, float> selectedUserIndexAndSimilarity = SelectTopNSimilarUsers(userIndex, targetUserSimilarities, topN);

            for (int i = 0; i < itemNumber; i++)
            {
                float? rating = null;
                if (userOriginalRatings[i] != null)
                {
                    rating = userOriginalRatings[i].Value;
                }
                else
                {
                    rating = CalculateFinalUserRatingForOneItem(i, targetUserAverageRating, userAverageRatings, selectedUserIndexAndSimilarity, predictedRatings);
                }
                finalRatings[i] = rating;
            }

            return finalRatings;
        }

        /// <summary>
        /// Calculates all final ratings.
        /// </summary>
        /// <param name="originalRatings">The exsiting real user- item rating matrix</param>
        /// <param name="userSimilarities">The similarities of all users.</param>
        /// <param name="predictedRatings">The dense user-item ratings matrix contains both user rated ratings and predicted ratings.</param>
        /// <param name="topN">The number of most similar neighbors.</param>
        /// <returns>The final ratings of all users to every items, contains both real ratings and predicted ratings.</returns>
        public float?[][] CalculateAllFinalRatings(int?[][] originalRatings, float?[][] userSimilarities, float?[][] predictedRatings, int topN)
        {
            int userNumber = predictedRatings.Length;
            int itemNumber = predictedRatings[0].Length;
            float?[][] finalAllPredictedRatings = new float?[userNumber][];

            float?[] userAverageRatings = CalculateUserAverageRatings(predictedRatings);

            for (int j = 0; j < userNumber; j++)
            {
                float?[] finalRatings = new float?[itemNumber];
                float targetUserAverageRating = userAverageRatings[j].Value;
                int?[] userOriginalRatings = originalRatings[j];
                float?[] targetUserSimilarities = userSimilarities[j];

                //Stores the indexes of selected users and their similarities to target user.
                Dictionary<int, float> selectedUserIndexAndSimilarity = SelectTopNSimilarUsers(j, targetUserSimilarities, topN);

                for (int i = 0; i < itemNumber; i++)
                {
                    float? rating = null;
                    if (userOriginalRatings[i] != null)
                    {
                        rating = userOriginalRatings[i].Value;
                    }
                    else
                    {
                        rating = CalculateFinalUserRatingForOneItem(i, targetUserAverageRating, userAverageRatings, selectedUserIndexAndSimilarity, predictedRatings);
                    }
                    finalRatings[i] = rating;
                }
                finalAllPredictedRatings[j] = finalRatings;
            }

            return finalAllPredictedRatings;
        }


        #endregion

        #region Private Methods

        /// <summary>
        /// Using Cosine fomulation to calculate the similarity between two items.
        /// </summary>
        /// <param name="itemOneIndex">The index of first item in matrix</param>
        /// <param name="itemTwoIndex">The index of second item in matrix</param>
        /// <param name="ratings">The exsiting user- item rating matrix</param>
        /// <param name="averageRatings">The average ratings of all users</param>
        /// <returns>The similarity between these two items</returns>
        private float? PearsonCorrelationItemSimilarity(int itemOneIndex, int itemTwoIndex, int?[][] ratings, float?[] averageRatings)
        {
            float? similarity = null;
            int userNumber = ratings.Length;
            int itemNumber = ratings[0].Length;

            float itemOneAverageRating = averageRatings[itemOneIndex].Value;
            float itemTwoAverageRating = averageRatings[itemTwoIndex].Value;

            float denominator = 0;
            float numeratorLeft = 0;
            float numeratorRight = 0;

            for (int k = 0; k < userNumber; k++)
            {
                if (ratings[k][itemOneIndex] != null && ratings[k][itemTwoIndex] != null)
                {
                    denominator += (ratings[k][itemOneIndex].Value - itemOneAverageRating) * (ratings[k][itemTwoIndex].Value - itemTwoAverageRating);
                    numeratorLeft += (ratings[k][itemOneIndex].Value - itemOneAverageRating) * (ratings[k][itemOneIndex].Value - itemOneAverageRating);
                    numeratorRight += (ratings[k][itemTwoIndex].Value - itemTwoAverageRating) * (ratings[k][itemTwoIndex].Value - itemTwoAverageRating);
                }
            }
            if (numeratorLeft * numeratorRight != 0)
            {
                similarity = (float)(denominator / (Math.Sqrt(numeratorLeft * numeratorRight)));
            }

            return similarity;
        }

        /// <summary>
        /// Calculates the average ratings of all items
        /// </summary>
        /// <param name="ratings"> the user-item rating matrix</param>
        /// <returns>The average ratings of all items</returns>
        private float?[] CalculateItemAverageRatings(int?[][] ratings)
        {
            int userNumber = ratings.Length;
            int itemNumber = ratings[0].Length;

            float?[] itemAverageRatings = new float?[itemNumber];

            for (int i = 0; i < itemNumber; i++)
            {
                float? average = null;
                float ratingSum = 0;
                float ratingNumber = 0;
                for (int j = 0; j < userNumber; j++)
                {
                    if (ratings[j][i] != null)
                    {
                        ratingSum += ratings[j][i].Value;
                        ratingNumber++;
                    }
                }
                average = ratingSum / ratingNumber;
                itemAverageRatings[i] = average;
            }

            return itemAverageRatings;
        }

        /// <summary>
        /// Using Cosine fomulation to calculate the similarity between two items.
        /// </summary>
        /// <param name="itemOneIndex">The index of first item in matrix</param>
        /// <param name="itemTwoIndex">The index of second item in matrix</param>
        /// <param name="ratings">The exsiting user- item rating matrix</param>
        /// <returns>The similarity between these two items</returns>
        private float? CosineItemSimilarity(int itemOneIndex, int itemTwoIndex, int?[][] ratings)
        {
            int userNumber = ratings.Length;
            int itemNumber = ratings[0].Length;
            float? similarity = null;

            //stores the ratings of the two items rated by a same user.
            List<List<int>> commonRatings = new List<List<int>>();

            for (int a = 0; a < userNumber; a++)
            {
                if (ratings[a][itemOneIndex].HasValue && ratings[a][itemTwoIndex].HasValue)
                {
                    List<int> rt = new List<int>();
                    rt.Add(ratings[a][itemOneIndex].Value);
                    rt.Add(ratings[a][itemTwoIndex].Value);
                    commonRatings.Add(rt);
                }
            }

            //applys the cosine formulation to calculate the similarity.
            if (commonRatings.Count != 0)
            {
                float denominator = 0;
                float numeratorLeft = 0;
                float numeratorRight = 0;

                foreach (List<int> twoRatings in commonRatings)
                {
                    denominator += twoRatings[0] * twoRatings[1];
                    numeratorLeft += (twoRatings[0] * twoRatings[0]);
                    numeratorRight += (twoRatings[1] * twoRatings[1]);
                }

                similarity = (float)(denominator / (Math.Sqrt(numeratorLeft * numeratorRight)));
            }

            return similarity;
        }

        /// <summary>
        /// Predicts the rating of a user to an item using item based aggregation algorithm.
        /// </summary>
        /// <param name="userIndex">Index of user in user- item rating matrix</param>
        /// <param name="itemIndex">Index of item in user- item rating matrix</param>
        /// <param name="userRatings">The real ratings of target user in user- item rating matrix</param>
        /// <param name="itemSimilarities">The similarities of target item to other items</param>
        /// <param name="topN">The number of most similar neighbors.</param>
        /// <returns>The predicted rating of target user to target item.</returns>
        private float PredictRating(int?[] userRatings, float?[] itemSimilarities, int topN)
        {
            float rating = 0;

            float[][] userNonNullRatings = GetNonNullRatingsAndSimilarities(userRatings, itemSimilarities);
            SortRatings(userNonNullRatings);

            float denominator = 0;
            float numerator = 0;

            for (int j = 0; j < topN && j < userNonNullRatings.Length; j++)
            {
                denominator += (userNonNullRatings[j][0] * userNonNullRatings[j][1]);
                numerator += userNonNullRatings[j][1];
            }
            if (numerator != 0)
            {
                rating = denominator / numerator;
            }
            else
            {
                rating = GetAverageRating(userRatings);
            }

            return rating;
        }

        /// <summary>
        /// Calculates the average rating of a user
        /// </summary>
        /// <param name="userRatings">All ratings of the user</param>
        /// <returns>The average rating of target user</returns>
        private float GetAverageRating(int?[] userRatings)
        {
            int itemNumber = userRatings.Length;

            float userAverageRatings = 0;
            float ratingSum = 0;
            float ratingNumber = 0;

            for (int j = 0; j < itemNumber; j++)
            {
                if (userRatings[j] != null)
                {
                    ratingSum += userRatings[j].Value;
                    ratingNumber++;
                }
            }
            userAverageRatings = ratingSum / ratingNumber;

            return userAverageRatings;
        }

        /// <summary>
        /// Sorts the ratings by similarities in decending order.
        /// </summary>
        /// <param name="array"></param>
        private void SortRatings(float[][] array)
        {
            int length = array.Length;
            for (int i = 0; i <= length - 2; i++)
            {
                for (int j = length - 1; j >= 1; j--)
                {
                    if (array[j][1] > array[j - 1][1])
                    {
                        float[] temp = array[j];
                        array[j] = array[j - 1];
                        array[j - 1] = temp;
                    }
                }
            }
        }

        /// <summary>
        /// Gets the ratings of user rated items and the their similarities to target item.
        /// </summary>
        /// <param name="userRatings">The real ratings of target user in user- item rating matrix</param>
        /// <param name="itemSimilarities">The similarities of all items to target item</param>
        /// <returns>The ratings of user rated items and the their similarities to target item.</returns>
        private float[][] GetNonNullRatingsAndSimilarities(int?[] userRatings, float?[] itemSimilarities)
        {
            List<float[]> list = new List<float[]>();
            for (int i = 0; i < userRatings.Length; i++)
            {
                float[] ratingAndSimilarity = new float[2];
                if (userRatings[i] != null && itemSimilarities[i] != null && itemSimilarities[i].Value>0)
                {
                    ratingAndSimilarity[0] = userRatings[i].Value;
                    ratingAndSimilarity[1] = itemSimilarities[i].Value;
                    list.Add(ratingAndSimilarity);
                }
            }
            return list.ToArray();
        }

        /// <summary>
        /// Calculates the average rating of every user.
        /// </summary>
        /// <param name="predictedRatings">The dense user-item ratings matrix contains both user rated ratings and predicted ratings.</param>
        /// <returns>The average rating of every user</returns>
        private float?[] CalculateUserAverageRatings(float?[][] predictedRatings)
        {
            int userNumber = predictedRatings.Length;
            int itemNumber = predictedRatings[0].Length;

            float?[] userAverageRatings = new float?[userNumber];

            for (int i = 0; i < userNumber; i++)
            {
                float? average = null;
                float ratingSum = 0;
                float ratingNumber = 0;
                for (int j = 0; j < itemNumber; j++)
                {
                    if (predictedRatings[i][j] != null)
                    {
                        ratingSum += predictedRatings[i][j].Value;
                        ratingNumber++;
                    }
                }
                average = ratingSum / ratingNumber;
                userAverageRatings[i] = average;
            }

            return userAverageRatings;
        }

        /// <summary>
        /// Calculate the similarity between two users using Pearson correlation fomulation.
        /// </summary>
        /// <param name="userOneAverageRating">The average rating of the first user.</param>
        /// <param name="userTwoAverageRating">The average rating of the second user.</param>
        /// <param name="userOneRatings">The ratings of first user in the dense user-item ratings matrix contains
        /// both user rated ratings and predicted ratings.</param>
        /// <param name="userTwoRatings">The ratings of first user in the dense user-item ratings matrix contains 
        /// both user rated ratings and predicted ratings.</param>
        /// <returns> The similarity between these two users</returns>
        private float? CalculateTwoUserSimilarity(float? userOneAverageRating, float? userTwoAverageRating, float?[] userOneRatings, float?[] userTwoRatings)
        {
            float? similarity = null;
            int itemNumber = userOneRatings.Length;

            float denominator = 0;
            float numeratorLeft = 0;
            float numeratorRight = 0;

            for (int j = 0; j < itemNumber; j++)
            {
                if ((userOneRatings[j] != null) && (userTwoRatings[j] != null) )
                {
                    denominator += (userOneRatings[j].Value - userOneAverageRating.Value) * (userTwoRatings[j].Value - userTwoAverageRating.Value);
                    numeratorLeft += (userOneRatings[j].Value - userOneAverageRating.Value) * (userOneRatings[j].Value - userOneAverageRating.Value);
                    numeratorRight += (userTwoRatings[j].Value - userTwoAverageRating.Value) * (userTwoRatings[j].Value - userTwoAverageRating.Value);
                }
            }
            similarity = (float)(denominator / Math.Sqrt(numeratorLeft * numeratorRight));

            return similarity;
        }

        /// <summary>
        /// Calculates the final ratings of a sepecific item to target user.
        /// </summary>
        /// <param name="itemIndex">The index of target item in user-item rating matrix.</param>
        /// <param name="targetUserAverageRating">The average rating of the target user.</param>
        /// <param name="userAverageRatings">The average ratings of the every user.</param>
        /// <param name="selectedUserIndexAndSimilarity">the indexes of top N neighbor users and their similarities to target user</param>
        /// <param name="predictedRatings">The dense user-item ratings matrix contains both user rated ratings and predicted ratings.</param>
        /// <returns> The final ratings of a sepecific item to target user</returns>
        private float? CalculateFinalUserRatingForOneItem(int itemIndex, float targetUserAverageRating, float?[] userAverageRatings, Dictionary<int, float> selectedUserIndexAndSimilarity, float?[][] predictedRatings)
        {
            float? rating = targetUserAverageRating;

            float denominator = 0;
            float numerator = 0;

            foreach (KeyValuePair<int, float> item in selectedUserIndexAndSimilarity)
            {
                float? comparisionUserRating = predictedRatings[item.Key][itemIndex];
                float? comparisionUserAverageRating = userAverageRatings[item.Key].Value;
                float? userSimilarity = item.Value;
                if (comparisionUserRating != null && comparisionUserAverageRating != null && userSimilarity != null && userSimilarity>0)
                {
                    denominator += (comparisionUserRating.Value - comparisionUserAverageRating.Value) * userSimilarity.Value;
                    numerator += userSimilarity.Value;
                }
            }

            rating += (denominator / numerator);

            return rating;
        }

        /// <summary>
        /// selects  the indexes of top N neighbor users and their similarities to target user.
        /// </summary>
        /// <param name="userIndex">The index of target user in user-item rating matrix.</param>
        /// <param name="userSimilarities">The similarities of every user to target user.</param>
        /// <param name="predictedRatings">The dense user-item ratings matrix contains both user rated ratings and predicted ratings.</param>
        /// <param name="topN">The number of most similar neighbors.</param>
        /// <returns>a Dictionary contains the index and similarity to target user of the selected users</returns>
        private Dictionary<int, float> SelectTopNSimilarUsers(int userIndex, float?[] userSimilarities, int topN)
        {
            Dictionary<int, float> selectedUserIndexAndSimilarity = new Dictionary<int, float>();

            int userNumber = userSimilarities.Length;
            Dictionary<int, float> similarityAndIndex = new Dictionary<int, float>();
            for (int i = 0; i < userNumber; i++)
            {
                if (i != userIndex)
                {
                    similarityAndIndex.Add(i, userSimilarities[i].Value);
                }
            }
            var result = from pair in similarityAndIndex orderby pair.Value select pair;
            var reversedResult = result.Reverse();

            foreach (KeyValuePair<int, float> pair in reversedResult)
            {
                if (selectedUserIndexAndSimilarity.Count < topN)
                {
                    selectedUserIndexAndSimilarity.Add(pair.Key, pair.Value);
                }
                else
                {
                    break;
                }
            }

            return selectedUserIndexAndSimilarity;
        }

        #endregion
    }
}
